package com.skh.bit;

/**
 * @Author: skh
 * @Date: 2020/3/12 10:28
 * @Description: 位1的个数
 */
public class HammingWeight {

    /**
     * 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：00000000000000000000000000001011
     * 输出：3
     * 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
     * 示例 2：
     *
     * 输入：00000000000000000000000010000000
     * 输出：1
     * 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
     * 示例 3：
     *
     * 输入：11111111111111111111111111111101
     * 输出：31
     * 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
     *  
     *
     * 提示：
     *
     * 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
     * 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
     *
     */

    /*
    方法 1：循环和位移动
    思路:我们遍历数字的 32 位。如果某一位是 11 ，将计数器加一。
    任何数字跟掩码 1进行逻辑与运算，都可以让我们获得这个数字的最低位。检查下一位时，我们将掩码左移一位。
     */
    public int hammingWeight(int n) {
        int bit = 0;
        int mask = 1;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) {
                bit++;
            }
            mask<<=1; //或者 mask*=2;
        }

        return bit;
    }


    /**
     * 位操作的小技巧
     * 我们不再检查数字的每一个位，而是不断把数字最后一个 1反转，并把答案加一。
     * 当数字变成 0的时候，我们就知道它没有 11 的位了，此时返回答案。
     * 这里关键的想法是对于任意数字 n，将 n 和 n−1 做与运算，会把最后一个 1的位变成 0
     * @param n
     * @return
     */
    public int hammingWeight2(int n) {
        int bit = 0;
        while (n != 0) {
            bit++;
            n = n & (n-1);
        }

        return bit;
    }

    //使用java自带的API
    public int hammingWeight3(int n) {
       return  Integer.bitCount(n);
    }

}
